package org.example.myleet.p850;

import java.util.*;

public class Solution {

    private static final long MODULO = 1000000007;

    public int rectangleArea(int[][] rectangles) {
        int n = rectangles.length;
        //扫描线方法解决。首先找到所有扫描点，去重、排序
        Set<Integer> scanXSet = new HashSet<>(n * 2);
        for (int[] rectangle : rectangles) {
            scanXSet.add(rectangle[0]);
            scanXSet.add(rectangle[2]);
        }
        List<Integer> scanXes = new ArrayList<>(scanXSet);
        scanXes.sort(Comparator.naturalOrder());
        long area = 0L;
        for (int i = 0; i < scanXes.size() - 1; ++i) {
            //逐点扫描，先计算两个点之间的横向距离
            int x1 = scanXes.get(i);
            int x2 = scanXes.get(i + 1);
            int deltaX = x2 - x1;
            //然后在这个扫描范围内找到所有矩形覆盖的范围ranges
            List<int[]> ranges = new ArrayList<>();
            for (int[] rectangle : rectangles) {
                if (rectangle[0] <= x1 && x2 <= rectangle[2]) {
                    ranges.add(new int[]{rectangle[1], rectangle[3]});
                }
            }
            //sort and merge ranges
            ranges.sort(Comparator.comparingInt(o -> o[0]));
            List<int[]> mergedRanges = new ArrayList<>();
            if (ranges.size() < 1) {
                continue;
            }
            //逐个range计算覆盖面积，累加
            int[] range = ranges.get(0);
            for (int j = 1; j < ranges.size(); ++j) {
                int[] r = ranges.get(j);
                if (r[0] <= range[1]) {
                    if (range[1] < r[1]) {
                        range[1] = r[1];
                    }
                } else {
                    mergedRanges.add(range);
                    range = r;
                }
            }
            mergedRanges.add(range);
            for (int[] r : mergedRanges) {
                int deltaY = r[1] - r[0];
                area += (long) deltaX * (long) deltaY;
                area %= MODULO;
            }
        }
        return (int) area;
    }
}
